package chapter02;

public class MySqrt69 {
    /**
     * 二分查找
     * 区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
     * 区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
     * left=0 right=x
     * mid=(left+right+1)/2
     * 1).mid*mid==x
     *  return x
     * 2).mid*mid>x
     *  right=mid-1
     * 3).mid*mid<x
     *  left=mid
     * 特别判断x==Max_Value
     *  return 46340
     */
    public int mySqrt(int x) {
        if(x==Integer.MAX_VALUE){
            return 46340;
        }
        int left=0,right=x;
        while (left<right){
            int mid=(left+right+1)/2;
            if((long)mid*mid==x){
                return mid;
            }else if((long)mid*mid<x){
                left=mid;
            }else{
                right=mid-1;
            }
        }
        return left;
    }
}
